import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 根据身高重建队列 {

    /**
     * https://leetcode.cn/problems/queue-reconstruction-by-height/
     * 排序 + 贪心, 主要是不好想
     */


    //我开始写的, 代码可以简化
    public static int[][] reconstructQueue(int[][] people) {
        //从高到低排序, 然后前面高度小到大排序
        Arrays.sort(people,(x,y) -> {
            if(x[0] - y[0] == 0){
                return x[1] - y[1];
            }
            return y[0] - x[0];
        });
        //创立一个动态的,都添加进去
        List<int[]> ret = new ArrayList<>();
        for (int[] num : people){
            ret.add(num);
        }
        for (int i = 0; i < people.length; i++) {
            int cur = ret.get(i)[1];//比你高的有几人
            //发现比你高的更多, 重新插入再删除
            if(cur < i){
                ret.add(cur,ret.get(i));
                ret.remove(i + 1);//因为先插入元素了
            }
        }
        //填入原数组
        int cnt = 0;
        for(int[] num : ret){
            people[cnt++] = num;
        }
        return people;
    }

    public static int[][] reconstructQueue1(int[][] people) {
        //从高到低排序, 然后前面高度小到大排序
        Arrays.sort(people,(x,y) -> {
            if(x[0] - y[0] == 0){
                return x[1] - y[1];
            }
            return y[0] - x[0];
        });
        //创立一个动态的,都添加进去
        List<int[]> ret = new ArrayList<>();
        for (int[] num : people){
            ret.add(num[1],num);
        }
        int cnt = 0;
        for(int[] num : ret){
            people[cnt++] = num;
        }
        return people;
    }

    public static void main(String[] args) {
        int[][] people = {
                {7, 0},
                {4, 4},
                {7, 1},
                {5, 0},
                {6, 1},
                {5, 2}
        };
        reconstructQueue(people);
    }
}
